# 热题100 https://leetcode.cn/studyplan/top-100-liked/
# 2/100 哈希-字母异位词分组
# leetcode第49题: https://leetcode.cn/problems/group-anagrams/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/13

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    def is_same_char(str1, str2):
        if len(str1) != len(str2):
            return False
        for c in str1:
            # 将str2中的c字符删除，1表示count，指定替换的次数。如果没有指定，则默认会替换所有出现的 old 子字符串。
            str2 = str2.replace(c, '', 1)
        if str2 == '':
            return True
        else:
            return False

    n = len(strs)
    if n < 2:
        return [strs]
    result = [[strs[0]]]
    for i, word in enumerate(strs):  # 遍历每一个单词
        if i == 0:
            continue
        l, is_in = len(word), False
        for arr in result:  # 遍历结果数组
            if is_same_char(arr[0], word):
                arr.append(word)
                is_in = True
                break
        if not is_in:
            result.append([word])  # 如果是一个与之前字母不同的单词则加入一个新数组
    return result


def groupAnagrams_hash(strs: list[str]) -> list[list[str]]:
    n = len(strs)
    if n < 2:
        return [strs]
    mapping = {}
    for word in strs:
        key = ''.join(sorted(word))
        if key not in mapping.keys():
            mapping[key] = [word]
        else:
            mapping[key].append(word)

    return list(mapping.values())


if __name__ == '__main__':
    # print(groupAnagrams_wrong(["eat", "tea", "tan", "ate", "nat", "bat"]))
    # print("abbc".replace("b", '', 1))
    # print(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat", "tee", "te"]))
    print(groupAnagrams_hash(["eat", "tea", "tan", "ate", "nat", "bat", "tee", "te"]))
